package com.aaron.leetcode.lc64;

import java.util.Arrays;
import java.util.Random;

/**
 * @author liurong
 * @date 2022/1/21 9:58
 * @version:
 */
/*
    状态转移方程，递归|迭代
    重叠子问题，备忘录

    自顶向下动态规划解法（递归）

    自底向上的迭代解法
 */
/*
    现在给你输入一个二维数组grid，其中的元素都是非负整数，现在你站在左上角，只能向右或者向下移动，需要到达右下角。现在请你计算，经过的路径和最小是多少？
    空间换时间
    状态转移方程，递归|迭代
    重叠子问题，备忘录
    自顶向下动态规划解法（递归） √
    自底向上的迭代解法

    memo[m][n]:空间复杂度M*N
    计算m*n次dp():时间复杂度M*N

 */
public class Solution64_1 {

    static int[][] genMatrix(int m, int n, int randomNumberBound) {
        Random random = new Random();
        int[][] ans = new int[m][n];
        for (int i = 0; i < m; i++) {
            ans[i] = random.ints(n, 1, randomNumberBound).toArray();
        }
        return ans;
    }


    public static void main(String[] args) {
        int[][] grid = genMatrix(4, 5, 10);
        for (int[] row : grid) {
            Arrays.stream(row).forEach(t -> System.out.print(t + " "));
            System.out.println();
        }
        Solution64_1 solution64 = new Solution64_1();
        int ans = solution64.minPathSum(grid);
        System.out.println(ans);
    }

    //空间复杂度 O(MN)
    int[][] memo;


    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;

        memo = new int[m][n];
        for (int[] row : memo) {
            Arrays.fill(row, -1);
        }

        return dp(grid, m - 1, n - 1);
    }

    //从左上角位置 (0, 0) 走到位置 (i, j) 的最小路径和为 dp(grid, i, j)
    int dp(int[][] grid, int i, int j) {
        if (i == 0 && j == 0) {
            return grid[0][0];
        }
        if (i < 0 || j < 0) {
            return Integer.MAX_VALUE;
        }

        if (memo[i][j] != -1) {
            return memo[i][j];
        }

        memo[i][j] = Math.min(
                dp(grid, i - 1, j),
                dp(grid, i, j - 1))
                + grid[i][j];
        return memo[i][j];
    }

}

